package cn.dlc.com.heap;

/**
 * @author 邓立川
 * @date 2021/3/25 21:52
 * @desc 对堆中的元素进行排序
 */
public class HeapSort<T extends Comparable<T>> {

    // 排序的方法
    public static void sort(Comparable[] source){

        // 创建一个堆,长度为参数的
        Comparable[] heap = new Comparable[source.length + 1];
        // 使用数组source初始化这个堆
        createHeap(source, heap);

        // 记录没有排序的元素的最大索引
        int num = heap.length -1;

        // 当num为1的时候，表示其他的元素都从堆里面删掉了
        while(num != 1) {
            // 交换元素
            exchange(heap, 1, num);
            // 元素减少一个
            num--;
            // 对1位置处的元素进行下城
            sink(heap, 1, num);
            // 注意，这个地方，元素本身并没有被删掉，仅仅是放到了最后
        }

        // 将heap中的元素复制回数组中。注意这个长度
        System.arraycopy(heap, 1, source,0,source.length);
    }

    // 通过数组构造对应的堆
    private static void createHeap(Comparable[] source, Comparable[] heap){
        // 将source从第0个元素开始拷贝source.length个元素到heap，heap从1开始
        System.arraycopy(source, 0, heap, 1, source.length);
        // 依次对元素做下沉处理
        for (int i = (heap.length / 2); i > 0 ; i--) {
            // 一直下沉到最后一个元素
            sink(heap, i, heap.length - 1);
        }
    }

    // 对元素进行下沉处理,0-range范围内下沉
    private static void sink(Comparable[] heap, int target, int range) {

        // 如果有子节点
        while(2*target <= range){

            // 记录最大值的索引
            int max ;

            // 如果有右子结点
            if(range > 2*target+1) {
                if(less(heap, 2*target,2*target + 1)) {
                    max = 2*target + 1;
                } else {
                    max = 2*target;
                }
            } else {
                // 没有右子结点，那么就是只有左子节点
                max = 2*target;
            }

            if(less(heap, max, target)) {
                // 子节点更小，结束循环
                break;
            } else {
                //子节点更大
                exchange(heap, max, target);
                // 重新制定target，继续进行比较
                target = max;
            }
        }
    }

    // 判断i和j元素的大小
    private static boolean less(Comparable[] heap, int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }

    // 交换i和j的位置
    private static void exchange(Comparable[]heap, int i, int j) {
        Comparable t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }

}
